let arr = [1,7,5,3,9,15]
// function selectSort(arr){
//     let len = arr.length
//     for(let i=1;i<len;i++){
//         let preIndex = i - 1
//         let current = arr[i]
//         while(preIndex >= 0 && arr[preIndex] > current){
//             arr[preIndex + 1] = arr[preIndex]
//             preIndex--
//         }
//         arr[preIndex + 1] = current
//     }
//     return arr        
// }

function selectSort2(arr){
    let len = arr.length
    let current
    for(let i=1;i<len;i++){
        current = arr[i]
        for(let j=i-1;j>=0;j--){
            if(arr[j] > current){
                arr[j+1] = arr[j]
            }else{
                arr[j+1] = current
                break
            }
        }
    }
    return arr  
}
let a = selectSort2(arr)
console.log(a)

/*
时间复杂度   O(n^2)
最坏        O(n^2)
最好        O(n)
稳定
空间复杂度   O(1)
*/